A computer network is a geographically distributed collection of interconnected subnetworks for transporting data between nodes, such as computers. A local area network (LAN) is an example of such a sub-network; a plurality of LANs may be further interconnected by an intermediate network node, such as a router or switch, to extend the effective “size” of the computer network and increase the number of communicating nodes. The nodes typically communicate by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Each node typically comprises a number of basic components including a processor, a memory and an input/output (I/O) interface. To increase performance, a node (such as an intermediate network node) may embody a multiprocessor environment wherein a plurality (“pool”) of processors is coupled to at least one I/O interface and to a central load balancer. Load balancing is an issue that must be addressed in order to enable the efficient use of the processors of the node. In addition, several objectives must be considered when determining the processing “load”, i.e., the work or tasks, to be balanced across the multiple processors.
One objective is that each processor should be kept substantially equally “busy” to ensure that the entire workload is processed as quickly as possible. If there is sufficient work to be performed, distribution of tasks among the processors is straightforward, i.e., the work should be distributed evenly among the processors. In other words, roughly the same amount of processing tasks should be assigned to each processor. However, some tasks are relatively inactive compared to others, so the distribution of the tasks requires further planning. Furthermore, precedent constraints between different tasks (i.e., real time requirements, priorities—some tasks must be performed before others) must be considered when distributing the tasks among the processors to meet the objective. Data load traffic, such as packets, is transferred over the computer network, received at the I/O interface and forwarded to the processor pool for processing. The data traffic may comprise user information that, when received at the intermediate network node, is used to create a user session. Herein session, load and task are used interchangeably. An example of such a session may be a voice or packet “call” between two users over the computer network. Coupled to each I/O interface is a forwarding table containing information used to direct each user session to a particular processor of the pool.
The central load balancer updates the forwarding table information in response to creation of the user session. The updated information enables each interface associated with a node, upon receiving incoming data traffic associated with the session, to forward that traffic to the appropriate processor. The processor maintains, inter alia, state information pertaining to that created session. When new sessions are created in response to user data traffic received at the intermediate network node, the central load balancer is notified so that it may update a central database; the database then distributes information to each forwarding table associated with an I/O interface of the node.
An application particularly suited for this type of multiprocessor environment is a wireless networking application using, e.g., cellular phones to exchange information among users. For this type of application, the multiprocessor environment is configured to provide session processing operations for each user. Wireless networks perform functions similar to that of “wired” networks in that the atmosphere, rather than the wires, provides a path over which the data may flow. Of course, the atmosphere is shared by many users using techniques that facilitate the sharing. Examples of a shared wireless network include a wireless local area network (WLAN) and a wireless asynchronous transfer mode (WATM) network. An example of a wireless access technique is the IEEE 802.16 standard for broadband wireless access (BWA).
The central load balancer is typically a general-purpose processor that is configured to execute various load-balancing algorithms, such as known round robin or statistic based distribution algorithms. However, a problem with such algorithms is that they do not take into consideration the “states” of the sessions. That is, although the number of sessions may have been balanced across the processors according to the algorithm(s), some of the sessions may be active, some relatively inactive and some completely inactive. For example, even though each processor within the processor pool may be assigned the same number of sessions, one processor may have a majority of active sessions (i.e., sessions exchanging information), whereas another processor may have a majority of inactive or “quiescent” sessions (i.e., sessions with no exchange of information).
Thus equally distributing the sessions or tasks does not equally distribute the active work among the processor resources. To address this problem, the central load balancer may be configured to gather and monitor the states of the sessions assigned to each processor by utilizing a software-based pooling algorithm. However, this solution is expensive by consuming resources on behalf of the central load balancer and each processor of the processor pool. For example, the central load balancer may utilize resources of the node to store the sessions themselves and to constantly monitor the states of the sessions executing on the processors by, e.g., accessing information from memories associated with the processors. The sessions' state information, such as statistics indicating the activity associated with each session, would be routinely accessed by the central balancer.
Moreover, each processor consumes “overhead” when obtaining the statistics gathered by the central load balancer. For example, the processors may use counters to obtain statistics, such as the number of times a packet associated with a session is processed, the number of packets associated with the session and/or the size of the packets associated with the sessions. Such overhead further consumes resources of the intermediate network node that may otherwise be used to perform useful processing operations. In addition, when the central load balancer accesses the memories to acquire the statistical information, that information is usually retrieved “in-band,” i.e., over the data path used to transport the packets throughout the node. Utilization of the in-band data path to transport statistics also consumes bandwidth associated with that resource.
In a typical wireless application, there may be a substantial number (e.g., hundreds of thousands) of sessions stored in the memories of the processor pool. Thus, it would be quite time consuming and expensive (in terms of resource consumption) for the central load balancer to access these memories to gather statistics used to determine the activity of the various sessions.
In summary memory storage space, memory (read, write, modify) cycles, data path capacity, and processor cycles are resources consumed by these known techniques directed towards load balancing in multiprocessor networks.
The present invention is directed to an efficient solution to this problem; in particular, the present invention provides a technique that efficiently monitors the active/inactive status of sessions distributed among the processors of a multiprocessor environment.